0670. 最大交换【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

1. 给定数字的范围是 $[0,{10}^8]$

2. 🎯 s.1 - 贪心

c

int maximumSwap(int num) {
    char s[12];
    sprintf(s, "%d", num);
    int len = strlen(s);
    int last[10];
    memset(last, -1, sizeof(last));
    for (int i = 0; i < len; i++) last[s[i] - '0'] = i;
    for (int i = 0; i < len; i++) {
        for (int d = 9; d > s[i] - '0'; d--) {
            if (last[d] > i) {
                char tmp = s[i]; s[i] = s[last[d]]; s[last[d]] = tmp;
                return atoi(s);
            }
        }
    }
    return num;
}

js

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function (num) {
  const digits = ('' + num).split('')
  const last = new Array(10).fill(-1)
  for (let i = 0; i < digits.length; i++) last[+digits[i]] = i
  for (let i = 0; i < digits.length; i++) {
    for (let d = 9; d > +digits[i]; d--) {
      if (last[d] > i) {
        ;[digits[i], digits[last[d]]] = [digits[last[d]], digits[i]]
        return +digits.join('')
      }
    }
  }
  return num
}

py

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        last = {int(d): i for i, d in enumerate(digits)}
        for i, d in enumerate(digits):
            for k in range(9, int(d), -1):
                if last.get(k, -1) > i:
                    digits[i], digits[last[k]] = digits[last[k]], digits[i]
                    return int(''.join(digits))
        return num

• 时间复杂度：$O(n)$，其中 n 是数字位数
• 空间复杂度：$O(n)$

算法思路：

• 记录每个数字 0-9 最后出现的位置
• 从高位到低位遍历，对每一位尝试找后方更大的数字交换，第一次交换即可返回